package _16_combination_sum_iii

func combinationSum3(k int, n int) [][]int {
	var res [][]int
	var list []int
	var helper func(k int, n int, list []int, startIndex int)

	helper = func(k int, n int, list []int, startIndex int) {
		if sum(list) == n && len(list) == k {
			tmp := make([]int, len(list))
			copy(tmp, list)
			res = append(res, tmp)
			return
		}

		for i := startIndex; i <= 9; i++ {
			// 由于要找到k个数的组合，所以从1到9遍历
			list = append(list, i)
			helper(k, n, list, i+1) // 这里的递归调用应该传入i+1而不是startIndex
			list = list[:len(list)-1]
		}
	}

	helper(k, n, list, 1)
	return res
}

func sum(list []int) int {
	var o int
	for _, v := range list {
		o += v
	}
	return o
}
